#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int rowHash[10];
int colHash[10];
int Hash[10];

class Solution {
    public:
        bool isValidSudoku(vector<vector<char> > &board1) {
            vector<vector<int> > board(9, vector<int>(9,0));

	for (int i = 0; i < 10; i++) {
	    rowHash[i] = 0;
	    colHash[i] = 0;
	    Hash[i] = 0;
	}

        for (int i = 0; i < board1.size(); i++) {
            for (int j = 0; j < board1.size(); j++) {
                if (board1[i][j] == ' ') board[i][j] = 0;
                 else board[i][j] = board1[i][j] - '0';
            }
        }

        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.size(); j++) {
		if (board[i][j] == 0) continue;
                if (rowHash[i] & (1<< board[i][j])) return false;
                else rowHash[i] |= 1 << board[i][j];
                if (colHash[j] & (1 << board[i][j])) return false;
                else colHash[j] |= 1 << board[i][j];
		int x = i/3;
		int y = j/3;
		int index = 3*x+y;
                if (Hash[index] & (1 << board[i][j])) return false;
		else Hash[index] |= 1 << board[i][j];
             }
        }
        return true;
    }
};

vector<char> trans(const string &str)
{
    vector<char> ans;
    for (int i = 0; i < str.size(); i++) {
        ans.push_back(str[i]);
    }
    return ans;
}

//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    vector<vector<char> > input(9);
    input[0] = trans("53  7    ");
    input[1] = trans("7  195   ");
    input[2] = trans(" 98    6 ");
    input[3] = trans("8   6   3");
    input[4] = trans("4  8 3  1");
    input[5] = trans("7   2   6");
    input[6] = trans(" 6    28 ");
    input[7] = trans("   419  5");
    input[8] = trans("    8  79");
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++){
            cout << input[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    bool result = mySolution.isValidSudoku(input);
    cout << result << endl;
    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
